package com.xk._02算法篇._04recrusion;

import com.xk.tools.Times;

/**
 * @description: 编写一个函数求第 n 项斐波那契数 1 1 2 3 5 8 13 21 ...
 * @author: xu
 * @date: 2022/10/15 21:31
 */
public class Fib {
    public static void main(String[] args) {
        Fib fib = new Fib();
        int n = 11;
        Times.test("fib0", () -> System.out.println(fib.fib0(n)));
        Times.test("fib1", () -> System.out.println(fib.fib1(n)));
        Times.test("fib2", () -> System.out.println(fib.fib2(n)));
        Times.test("fib3", () -> System.out.println(fib.fib3(n)));
        Times.test("fib4", () -> System.out.println(fib.fib4(n)));
        Times.test("fib5", () -> System.out.println(fib.fib5(n)));
    }

    // 时间：O(2^n) 空间：O(n) 递归
    public int fib0(int n){
        if (n <= 2) return 1;
        return fib0(n-1) + fib0(n-2);
    }

    // 时间：O(n) 空间：O(n) 递归
    public int fib1(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n+1];
        array[1] = array[2] = 1;
        return fib1(n, array);
    }
    private int fib1(int n, int[] array) {
        if (array[n] == 0) {
            array[n] = fib1(n-1, array) + fib1(n-2, array);
        }
        return array[n];
    }

    // 时间：O(n) 空间：O(n) 非递归
    public int fib2(int n){
        if (n <= 2) return 1;
        int[] array = new int[n+1];
        array[1] = array[2] = 1;
        for (int i = 3; i <= n; i++){
            array[i] = array[i-1] + array[i-2];
        }
        return array[n];
    }

    // 时间：O(n) 空间：O(1) 非递归 滚动数组
    public int fib3(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++){
            array[i % 2] = array[0] + array[1];
        }
        return array[n % 2];
    }

    // 时间：O(n) 空间：O(1) 非递归 滚动数组
    public int fib4(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++){
            // i % 2 <==> i & 1 (只能模2可以这么做)
            array[i & 1] = array[0] + array[1];
        }
        return array[n & 1];
    }

    // 时间：O(n) 空间：O(1) 非递归
    public int fib5(int n) {
        if (n <= 2) return 1;
        int first = 1, second = 1;
        while (n-- >= 3){
            second = first + second;
            first = second - first;
        }
        return second;
    }
}
